#pragma once
#include <type_traits>
#include <iostream>
using std::ostream;

#include "../public/constants.hpp"
#include "../public/exception.hpp"
#include "../allocator/defaloc.hpp"
#include "../iterator/iterator_traits.hpp"

#include <cmath>

namespace bla {
	const _containerSizeType _vectorDefaultCapacity = 16;

	template<typename _type>
	class vectorIterator {
	public:
		//using define
		using valueType = _type;
		using pointerType = _type * ;
		using referenceType = _type & ;
		using sizeType = _containerSizeType;
		using differenceType = _containerSizeType;

		//interface of all iteraters
		typedef valueType _valueType;
		typedef differenceType _difType;
		typedef _random_iterator_flag _category;

	private:
		//class data define: size of vectorIterator<> class: 8
		pointerType _data;
	public:
		inline pointerType getPtr() { return _data; };

		vectorIterator(pointerType p = nullptr) :_data(p) {};

		vectorIterator(const vectorIterator<_type>&) = default;
		vectorIterator<_type>& operator=(const vectorIterator<_type>&) = default;
		vectorIterator<_type>& operator=(pointerType p) {
			_data = p;
			return *this;
		}

		referenceType operator *() { return *_data; }
		const referenceType operator *()const { return *_data; }
		pointerType operator ->() { return &(operator*()); }
		const pointerType operator ->()const { return &(operator*()); }

		vectorIterator<_type>& operator ++() {
			++_data;
			return *this;
		};
		vectorIterator<_type> operator ++(int) {
			auto temp = *this;
			++(*this);
			return temp;
		};
		vectorIterator<_type>& operator --() {
			--_data;
			return *this;
		};
		vectorIterator<_type> operator --(int) {
			auto temp = *this;
			--(*this);
			return temp;
		};

		bool operator ==(const vectorIterator<_type>& it)const {
			return _data == it._data;
		};
		bool operator !=(const vectorIterator<_type>& it)const {
			return !(*this == it);
		};

	public:
		template<typename _type>
		friend vectorIterator<_type> operator + (
			const vectorIterator<_type>& it, typename vectorIterator<_type>::differenceType n);

		template<typename _type>
		friend vectorIterator<_type> operator + (
			typename vectorIterator<_type>::differenceType n, const vectorIterator<_type>& it);

		template<typename _type>
		friend vectorIterator<_type> operator - (
			const vectorIterator<_type>& it, typename vectorIterator<_type>::differenceType n);

		template<typename _type>
		friend vectorIterator<_type> operator - (
			typename vectorIterator<_type>::differenceType n, const vectorIterator<_type>& it);

		template<typename _type>
		friend typename vectorIterator<_type>::differenceType operator - (
			const vectorIterator<_type>& it1, const vectorIterator<_type>& it2);


		~vectorIterator() = default;
	};

	template<typename _type>
	vectorIterator<_type> operator+(const vectorIterator<_type>& it, typename vectorIterator<_type>::differenceType n)
	{
		vectorIterator<_type> ret(it);
		ret._data += n;
		return ret;
	}

	template<typename _type>
	vectorIterator<_type> operator+(typename vectorIterator<_type>::differenceType n, const vectorIterator<_type>& it)
	{
		vectorIterator<_type> ret(it);
		ret._data += n;
		return ret;
	}

	template<typename _type>
	vectorIterator<_type> operator-(const vectorIterator<_type>& it, typename vectorIterator<_type>::differenceType n)
	{
		vectorIterator<_type> ret(it);
		ret._data -= n;
		return ret;
	}

	template<typename _type>
	vectorIterator<_type> operator-(typename vectorIterator<_type>::differenceType n, const vectorIterator<_type>& it)
	{
		vectorIterator<_type> ret(it);
		ret._data -= n;
		return ret;
	}

	template<typename _type>
	typename vectorIterator<_type>::differenceType operator-(const vectorIterator<_type>& it1, const vectorIterator<_type>& it2)
	{
		return typename vectorIterator<_type>::differenceType(it1._data - it2._data);
	}

	/*
	 * template para:
	 * _type : all container have, can be any type
	 * _allocator: suggest using the default value: the default is _defaloc class
	 */
	template<typename _type, typename _allocator = _defaloc<_type>>
	class vector {
	public:
		//using define
		using iterator = vectorIterator<_type>;
		using sizeType = _containerSizeType;
		using differenceType = _containerSizeType;
		using valueType = _type;
		using pointerType = _type * ;
		using referenceType = _type & ;
	private:
		//predefined type/value
		//const sizeType _typeSize = sizeof(_type);

	private:
		//class data define: size of vector<> class: 32
		sizeType _capacity;
		sizeType _size;
		iterator _begin;
		_allocator _allocatorObject;

	private:
		/*
		 * "in default", capacity multiple by 2
		 */
		iterator _reAllocate() {
			this->_capacity *= 2;
			iterator _ptr = _allocatorObject._allocate(this->_capacity);
			return _ptr;
		}

		/*
		 * specified new capacity: c
		 */
		iterator _reAllocate(_containerSizeType c) {
			this->_capacity = c;
			iterator _ptr = _allocatorObject._allocate(this->_capacity);
			return _ptr;
		}

		/*
		 * destory and deallocate
		 */
		void _destroyAndDeallocate(iterator it, differenceType oldSize) {
			if (!std::is_trivially_destructible<_type>::value) {
				iterator _ptr = it;
				for (sizeType _index = 0; _index < oldSize; ++_index) {
					_allocatorObject._destroy((_ptr++).getPtr());
				}
			}
			_allocatorObject._deallocate(it.getPtr());
		}

		/*
		 * copyNew
		 */
		void _copyNew(iterator source, differenceType len, iterator target) {
			iterator _cptr = source;
			iterator _ptr = target;
			if (!std::is_trivially_copy_constructible<_type>::value) {
				for (sizeType time = 0; time < len; ++time) {
					_allocatorObject._construct((_ptr++).getPtr(), *(_cptr++));
				}
			}
			else {
				for (sizeType time = 0; time < len; ++time) {
					*(_ptr++) = *(_cptr++);
				}
			}
		}

		/*
		 * copyNew
		 */
		void _copyNew(valueType v, iterator target) {
			if (!std::is_trivially_copy_constructible<_type>::value) {
				_allocatorObject._construct(target.getPtr(), v);
			}
			else {
				*target = v;
			}
		}

		/*
		 * copyNew
		 */
		void _copyNew(iterator source, iterator sourceEnd, iterator target) {
			const differenceType len = sourceEnd - source;
			iterator _cptr = source;
			iterator _ptr = target;
			if (!std::is_trivially_copy_constructible<_type>::value) {
				for (sizeType time = 0; time < len; ++time) {
					_allocatorObject._construct((_ptr++).getPtr(), *(_cptr++));
				}
			}
			else {
				for (sizeType time = 0; time < len; ++time) {
					*(_ptr++) = *(_cptr++);
				}
			}
		}

		/*
		 * copy
		 */
		void _copy(iterator source, differenceType len, iterator target) {
			iterator _cptr = source;
			iterator _ptr = target;
			for (sizeType time = 0; time < len; ++time) {
				*(_ptr++) = *(_cptr++);
			}
		}

		/*
		 * copy
		 */
		void _copy(iterator source, iterator sourceEnd, iterator target) {
			const differenceType len = sourceEnd - source;
			iterator _cptr = source;
			iterator _ptr = target;
			for (sizeType time = 0; time < len; ++time) {
				*(_ptr++) = *(_cptr++);
			}
		}

	public:
		//inline _containerSizeType capacity() { return this->_capacity; };
		//inline _containerSizeType size() { return this->_size; };
		//inline _pointerType begin() { return this->_begin; };

		inline const sizeType capacity() const { return this->_capacity; };
		inline const sizeType size() const { return this->_size; };
		inline const iterator begin() const { return this->_begin; };
		inline const iterator end() const { return this->_begin + this->_size; };
		inline bool empty() const { return this->_size == 0; } //this->begin() == this->end()
		inline bool full() const { return this->_size == this->_capacity; }

		referenceType operator[] (differenceType n) {
			return *(begin() + n);
		}

		/*
		 * push_back: const _type& v
		 *     if not full, add a value/object in the end
		 *     else reallocate, then copy
		 */
		void push_back(const _type& v) {
			if (this->full()) { //should reallocate!
				iterator newIter = this->_reAllocate();
				this->_copyNew(this->begin(), this->_size, newIter);
				this->_destroyAndDeallocate(this->begin(), this->_size);
				this->_begin = newIter;
				this->push_back(v); //with size add inside
			}
			else {
				if (!std::is_trivially_copy_constructible<_type>::value) {
					_allocatorObject._construct((_begin + this->_size++).getPtr(), v);
				}
				else {
					*(_begin + this->_size++) = v;
				}
			}
		}

		/*
		 * push_back: iterator ptrv
		 *     if not full, add a value/object in the end
		 *     else reallocate, then copy
		 */
		void push_back(iterator ptrv) {
			if (this->full()) { //should reallocate!
				iterator newIter = this->_reAllocate();
				this->_copyNew(this->begin(), this->size, newIter);
				this->_destroyAndDeallocate(this->begin(), this->_size);
				this->begin() = newIter;
				this->push_back(*ptrv); //with size add inside
			}
			else {
				if (!std::is_trivially_copy_constructible<_type>::value) {
					_allocatorObject._construct((_begin + this->_size++).getPtr(), *ptrv);
				}
				else {
					*(_begin + this->_size++) = *ptrv;
				}
				return true;
			}
		}

		/*
		 * insert: iterator loc, const _type& v
		 *    if not full, add a value/object at the location of iterator
		 *    else reallocate, then copy
		 */
		void insert(iterator loc, const _type& v) {
			if (this->full()) { //should reallocate!
				iterator newIter = this->_reAllocate();
				this->_copyNew(this->begin(), loc, newIter);
				this->_copyNew(v, newIter + (loc - this->begin()));
				this->_copyNew(loc, this->end(), newIter + (loc - this->begin()) + 1);
				this->_destroyAndDeallocate(this->begin(), this->_size);
				++this->_size;
				this->_begin = newIter;
			}
			else if (this->end() == loc) { //equal push_back
				this->push_back(v);
			}
			else {
				differenceType lastIndex = this->_size - 1;
				differenceType targetIndex = loc - this->begin();
				//add back
				this->push_back(this->operator[](lastIndex));
				//all other, move one dis
				if (lastIndex > 0) {
					for (differenceType index = (lastIndex - 1); index >= targetIndex; --index) {
						this->operator[](index + 1) = this->operator[](index);
						if (index == 0) break;
					}
				}
				//substitute
				this->operator[](targetIndex) = v;
			}
		}

		/*
		 * insert: iterator loc, iterator ptrstart, iterator ptrend
		 *    if remain size is enough, add some value/objects at the location of iterator
		 *    else reallocate
		 *
		 *    if the iterator loc and ptrstart and ptrend are belong to the same vector, there will become bug
		 *        donot use it like this!
		 *    if ptrend <= ptrstart, there will become unknown bug!
		 */
		void insert(iterator loc, iterator ptrstart, iterator ptrend) {
			const differenceType insertNum = ptrend - ptrstart;
			if ((this->_capacity - this->_size) < insertNum) { //should reallocate!
				//caculate the target capacity
				_containerSizeType newCapacity = 2 * (_containerSizeType)pow(2, ((_containerSizeType)(log(this->_size + insertNum) / log(2))));

				iterator newIter = this->_reAllocate(newCapacity);
				this->_copyNew(this->begin(), loc, newIter);
				this->_copyNew(ptrstart, ptrend, newIter + (loc - this->begin()));
				this->_copyNew(loc, this->end(), newIter + (loc - this->begin()) + insertNum);
				this->_destroyAndDeallocate(this->begin(), this->_size);
				this->_size += insertNum;
				this->_begin = newIter;
			}
			else {
				const differenceType insertLoc = loc - this->begin();
				const differenceType maxMoveNum = this->end() - loc;
				if (maxMoveNum >= insertNum) {
					//pushback
					const differenceType pushbackStartLoc = this->_size - insertNum;
					differenceType startMoveLoc = pushbackStartLoc;
					for (differenceType time = 0; time < insertNum; ++time) {
						this->push_back(this->operator[](startMoveLoc++));
					}
					//move the remain
					if (pushbackStartLoc > 0) {
						for (differenceType index = pushbackStartLoc - 1; index >= insertLoc; --index) {
							this->operator[](index + insertNum) = this->operator[](index);
							if (index == 0) break;
						}
					}
					//substitute
					startMoveLoc = insertLoc;
					for (iterator iter = ptrstart; iter != ptrend; ++iter) {
						this->operator[](startMoveLoc++) = *iter;
					}
				}
				else {
					//pushback of some of new iterators
					iterator newiterLoc = ptrend - (insertNum - maxMoveNum);
					const differenceType pushbackStartLoc = this->_size - maxMoveNum;
					for (differenceType time = 0; time < (insertNum - maxMoveNum); ++time) {
						this->push_back(*(newiterLoc++));
					}
					//pushback the origin remain value of vector
					differenceType startMoveLoc = pushbackStartLoc;
					for (differenceType time = 0; time < maxMoveNum; ++time) {
						this->push_back(this->operator[](startMoveLoc++));
					}
					//substitute
					startMoveLoc = insertLoc;
					newiterLoc = ptrend - (insertNum - maxMoveNum);
					for (iterator iter = ptrstart; iter != newiterLoc; ++iter) {
						this->operator[](startMoveLoc++) = *iter;
					}
				}
			}
		}

		/*
		 * pop_back
		 *     if not empty, erase a value/object in the end, return true
		 *     else return false
		 */
		bool pop_back() {
			if (this->empty()) return false;
			else {
				if (!std::is_trivially_destructible<_type>::value) {
					_allocatorObject._destroy((this->_begin + this->_size - 1).getPtr());
				}
				this->_size--;
				return true;
			}
		}

		/*
		 * erase: iterator loc
		 *    if not empty, erase a value/object in the end, return true
		 *    else return false
		 */
		bool erase(iterator loc) {
			if (this->empty()) return false;
			else if ((this->end() - 1) == loc) { //equal push_back
				return this->pop_back();
			}
			else {
				//all other, move one dis
				for (differenceType index = (loc - this->begin()); index < (this->_size - 1); ++index) {
					*(_begin + index) = *(_begin + index + 1);
				}
				//pop_back
				this->pop_back();
				return true;
			}
		}

		/*
		 * erase: iterator ptrstart, iterator ptrend
		 *    if not empty, erase some value/objects, return true
		 *    else return false
		 *    if ptrend <= ptrstart, there will become unknown bug!
		 */
		bool erase(iterator ptrstart, iterator ptrend) {
			if (this->empty()) return false;
			else {
				const differenceType eraseNum = ptrend - ptrstart;
				//substitute
				differenceType substituteIndex = ptrstart - this->begin();
				for (; substituteIndex < this->size() - eraseNum; ++substituteIndex) {
					this->operator[](substituteIndex) = this->operator[](substituteIndex + eraseNum);
				}
				//pop_back
				for (differenceType time = 0; time < eraseNum; ++time) {
					this->pop_back();
				}
				return true;
			}
		}

		/*
		 * default construction function:
		 *     init private values, call function of _allocatorObject to allocate memory,
		 *         if _type is not trivially_constructible, should call _construct of _allocatorObject
		 */
		vector() :
			_capacity(_vectorDefaultCapacity), _size(0), _begin(nullptr), _allocatorObject(_allocator())
		{
			iterator _ptr = _allocatorObject._allocate(this->_capacity);
			this->_begin = _ptr;
		}

		/*
		 * copy construction function:
		 */
		vector(const vector<_type, _allocator>& _cpa) :
			_capacity(_cpa.capacity()), _size(0), _begin(nullptr), _allocatorObject(_allocator())
		{
			iterator _ptr = _allocatorObject._allocate(this->_capacity);
			this->_begin = _ptr;

			iterator _cptr = _cpa.begin();
			if (!std::is_trivially_copy_constructible<_type>::value) {
				for (sizeType _index = this->_size; _index < _cpa.size(); ++_index) {
					_allocatorObject._construct((_ptr++).getPtr(), *(_cptr++));
				}
			}
			else {
				for (sizeType _index = this->_size; _index < _cpa.size(); ++_index) {
					*(_ptr++) = *(_cptr++);
				}
			}
			this->_size = _cpa.size();
		}

		/*
		 * = assign function
		 *  compare &_cpa and this first, if address of these two pointers are same, do nothing
		 *                                if not, campare this->_size and _cpa.size(), then decide to:
		 *                                    use = of _type and allocate/deallocate of _allocatorObject
		 */
		vector<_type, _allocator>& operator= (const vector<_type, _allocator>& _cpa) {
			if (&_cpa == this)
				return *this;
			else {
				if (this->_size < _cpa.size()) {
					if (this->_capacity >= _cpa.size()) {
						iterator _ptr = this->_begin;
						iterator _cptr = _cpa.begin();
						if (!std::is_trivially_copy_constructible<_type>::value) {
							for (sizeType _index = this->_size; _index < _cpa.size(); ++_index) {
								_allocatorObject._construct((_ptr++).getPtr(), *(_cptr++));
							}
						}
						else {
							for (sizeType _index = this->_size; _index < _cpa.size(); ++_index) {
								*(_ptr++) = *(_cptr++);
							}
						}
						this->_size = _cpa.size();
					}
					else { //this->capacity < _cpa.size(), should reallocate!
						iterator newIter = this->_reAllocate(_cpa.capacity());
						this->_copyNew(_cpa.begin(), _cpa.end(), newIter);
						this->_destroyAndDeallocate(this->begin(), this->_size);
						this->_size = _cpa.size();
						this->_begin = newIter;
					}
				}
				else {  //this->size >= _cpa.size()
					iterator _ptr = this->_begin;
					iterator _cptr = _cpa.begin();
					for (sizeType _index = 0; _index < _cpa.size(); ++_index) {
						*(_ptr++) = *(_cptr++);
					}
					if (!std::is_trivially_destructible<_type>::value) {
						for (sizeType _index = _cpa.size(); _index < this->_size; ++_index) {
							_allocatorObject._destroy((_ptr++).getPtr());
						}
					}
					this->_size = _cpa.size();
				}
				return *this;
			}
		}

		/*
		 * deconstruction function:
		 *  call function of _allocatorObject to deallocate memory,
		 *    if _type is not trivially_destructible, should call _destroy of _allocatorObject
		 */
		~vector() {
			if (!std::is_trivially_destructible<_type>::value) {
				iterator _ptr = this->_begin;
				for (sizeType _index = 0; _index < this->_size; ++_index) {
					_allocatorObject._destroy((_ptr++).getPtr());
				}
			}
			_allocatorObject._deallocate((this->_begin).getPtr());
			this->_begin = nullptr;
		}

		template<typename _type, typename _allocator = _defaloc<_type>>
		friend ostream& operator<< (ostream &os, const vector<_type, _allocator>& a);
	};

	template<typename _type, typename _allocator = _defaloc<_type>>
	ostream & operator<<(ostream & os, typename const vector<_type, _allocator>& a)
	{
		typename vector<_type, _allocator>::iterator iter = a.begin();
		for (; iter != a.end(); ++iter) {
			os << *iter << " ";
		}
		return os;
	}
}
